Algorithms controlling cache behavior have traditionally been of interest to computer scientists. Particularly, research has focused on a question at the root of cache behavior as to how to predict what resources will be accessed next. This issue drives both choosing which items to evict from a cache when it reaches the limits of its size, as well as techniques for selectively populating the cache with items in advance of their expected need.
In general, a cache is a region of relatively fast data storage used to store frequently used items from a larger region of relatively slow data storage. Without loss of generality, these regions could be main memory and a disk, a processor cache and main memory, etc; their performance relative to each other is important.
Recommended algorithms have been used to create static pre-computations of item relationships that implement a large amount of storage and typically cannot be done in real time. This static pre-computation, which traditionally builds and stores a matrix of item relationships, is too space inefficient and complex to use as a cache prediction mechanism for anything but the most expensive cached results. Static pre-computation also suffers from a very serious problem of being insufficiently reactive to changes in system behavior, which ultimately undermines its effectiveness as a cache prediction algorithm in all but the most coarse-grained contexts.
In order for a cache prediction algorithm to logically be useful, it should be cheaper to compute than the operation itself. Traditionally, most cache prediction mechanisms have focused on very cheap first-order approximations of the relative usefulness of a given cache entry. The usefulness of a cache entry is almost always defined by its probability of subsequent access. In order to do this, traditional cache prediction mechanisms focus on how recently a given item was accessed, or on statistics of data page sizes and very high-level approximations.
For example, devices in I/O paths generally pre-fetch as much data as possible: a 1 KB read from an application might be turned into an 8 KB read in the operating system (with the remaining 7 KB cached), and the disk that actually satisfies the request might read 64 KB from the platters into its local memory. This is a performance advantage because the latency associated with preparing to satisfy a disk request is quite high since it is advantageous to read as much data as possible while the heads and platters are in the correct configuration.
This is a performance advantage because the differences in latencies are very high, and there is generally a computational (rather than I/O) component that separates I/O requests. This simple scheme is based on the principle of spatial locality such that items that are accessed together tend to be located together (for example, if you read the third paragraph of this document, you are likely to read the fourth paragraph as well). Unfortunately, that scheme is not able to pre-fetch the next document you will read because the latency involved in getting the next document might be quite significant, as no caching is available to help.
Therefore what has been needed is a system and method for the dynamic generation of correlation scores between arbitrary objects to create a list of correlated items.